package gold.digger;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC322 {

    public int coinChange(int[] coins, int amount) {
        if (amount <= 0) {
            return 0;
        }

        int[] memo = new int[amount + 1];
        for (int i = 0; i <= amount; i++) {
            memo[i] = amount + 2;
        }

        memo[0] = 0;
        for (int i = 0; i <= amount; i++) {
            for (int coin : coins) {
                if (i - coin < 0) {
                    continue;
                }
                memo[i] = Math.min(memo[i], memo[i - coin] + 1);
            }
        }

        return memo[amount] == amount + 2 ? -1 : memo[amount];
    }

    public int coinChangeDP(int[] coins, int amount, int[] memo) {
        if (amount == 0) {
            return 0;
        }

        if (amount < 0) {
            return -1;
        }

        if (memo[amount] > 0) {
            return memo[amount];
        }

        int res = Integer.MAX_VALUE;
        for (int coin : coins) {
            int subRes = coinChangeDP(coins, amount - coin, memo);
            if (subRes == -1) {
                continue;
            }
            res = Math.min(res, 1 + subRes);
        }

        memo[amount] = res == Integer.MAX_VALUE ? -1 : res;
        return memo[amount];
    }

    public static void main(String[] args) {
        LC322 an = new LC322();
        int[] coins = {186, 419, 83, 408};
        System.out.println(an.coinChange(coins, 6249));

    }
}
